// 解题思路：
// 贪心策略：使用小根堆，每次找到最小的数，加负号
// 加完负号后，再次放入到堆中，下次再找最小的数加负号，一共 k 次
// 最终返回堆中所有数的和

// 解题思路 2：
// 分类讨论：
// 如果负数的个数 count > k，把数组升序排序，前 k 个负数改成正数即可
// 如果负数的个数 count <= k，把所有的负数都改成正数，判断 k - count 是否为奇数
// 如果是奇数，就将最小元素的改成负数
// 如果是偶数，直接忽略

import java.util.*;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> a - b);
        for(int x : nums) heap.offer(x);
        while(k-- > 0){
            int t = heap.poll();
            heap.offer(-t);
        }
        int ret = 0;
        while(!heap.isEmpty()){
            int t = heap.poll();
            ret += t;
        }
        return ret;
    }

    public int largestSumAfterKNegations2(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        int min = 100;
        int ret = 0;

        for(int x : nums){
            if(x < 0) count++;
            min = Math.min(min, Math.abs(x));
        }

        if(count > k){
            Arrays.sort(nums);
            for(int i = 0; i < k; i++){
                ret += Math.abs(nums[i]);
            }
            for(int i = k; i < n; i++){
                ret += nums[i];
            }
        }else{
            for(int i = 0; i < n; i++){
                ret += Math.abs(nums[i]);
            }
            if((count - k) % 2 != 0) ret -= 2 * min;
        }
        return ret;
    }
}
